Collaborative editing systems have been used to allow multiple users to simultaneously update shared data. For example, the users may be collaborating to generate a text document in which the users may be modifying various portions of the text document simultaneously. Several different models can be used in collaborative editing systems. In a centralized model, a server computer system maintains a master copy of the document and each user's client computer system maintains a slave copy. When a user requests to modify the document, the user's client computer system sends a modify request to the server computer system. Upon receiving the modify request, the server computer system modifies the master copy of the document and sends a modify notification to each client computer system. Upon receiving the modify notification, a client computer system updates its local copy of the document. The disadvantage of the centralized model is that a user who modifies a document needs to wait until the corresponding modify notification from the server is received for the modification to take place. In many instances, the delay resulting from waiting for the modify notification can be unacceptable to the user. In a distributed model, each user's computer system maintains a local copy of the document. When a user modifies the document, it is immediately reflected in the local copy and a modify notification is sent to the other user computer systems. When those user computer systems receive the modify notification, they modify their local copy of the document accordingly. The distributed model has the advantage that users see the effects of their modifications immediately without having to wait for the delay inherent in a round-trip communication with a server computer system. The distributed model, however, is more complex than the centralized model because of conflicting modifications by users that need to be resolved.
Conflicting modifications occur in the distributed model because one user may be modifying a certain portion of a document and a different user may also be modifying that same portion of the document. For example, a first user may delete the third paragraph from the document at the same time that a second user is inserting a new paragraph before the first paragraph of the document. When the first user's computer system receives the notification to insert a new first paragraph, it does so. When the second user's computer system receives the notification to delete the third paragraph, if it proceeds to delete the third paragraph, it will delete what is now the second paragraph of the first user's local copy. As a result, the local copies of the first user and the second user will be inconsistent. Such editing operations are said to conflict.
The resolution of conflicting operations in a collaborative editing environment has been studied extensively. One technique for resolving conflicting operations is referred to as “operational transformation.” See C. A. Ellis and S. J. Gibbs, “Concurrency Control in Groupware Systems,” Proc. 1989 ACM SIGMOD International Conference on the Management of Data, June 1989, pp. 399-407. A collaborative editing system that uses operational transformation techniques transforms conflicting operations so that the local copies of the data are kept consistent when the document is in a quiescent state, that is, when all modifications have already been applied to all copies of the document. In the example above, when the second user's computer system receives the notification to delete the third paragraph, it will detect that the first user's computer system did not insert the paragraph before the first user deleted the third paragraph. As such, the second user's computer system can use operational transformation to transform the notification to delete the third paragraph into a notification to delete the fourth paragraph. When the second user's computer system then applies the transformed operation, it will delete the same paragraph that the first user deleted and the local copies of the document will thus be consistent.
The resolution of conflicting operations has, however, not been applied to resolving conflicts when only attributes or styles of the characters of a document are being modified. For example, a first user may want to italicize a certain sentence in the document, and a second user may want to bold the entire paragraph that contains the sentence. Traditionally, the modifying of the style of text in the document has been effected by simply replacing the text with the same text but with a new style. However, the replacing of text when only the style of the text changes may lead to undesirable and unnecessarily restricted outcomes. It would be desirable to have a technique for resolving conflicts related to the style of the text of the document and more generally to attributes of objects of data.